This invention generally relates to programmable logic arrays (PLAs), and particularly to minimizing the size and speed of PLAs.
Programmable Logic Arrays (PLAs) have been used in the semiconductor industry for many years. They are essentially generic electronic circuits, able to be programmed to provide a variety of logic functions. PLAs are well understood in the art, but a brief explanation is provided below.
In PLAs, a logic function to be implemented is expressed in product terms (AND terms) and sum terms (OR terms). Each product term is generated by circuitry that can be programmed to form the AND of any subset of the inputs to the PLA and their complements. Product terms are then be summed, or OR""d, through additional programmable circuitry.
More specifically, PLAs are generally constructed in the form of regular arrays, with the input lines being orthogonal to the product lines, as shown in the generalized circuit diagram of FIG. 1. FIG. 1 shows one type of PLA known as a PAL. In FIG. 1, PAL 100 includes inputs 102, A-D, where each input and its complement is input into programmable AND array 104 on lines 106. AND lines 108 are formed orthogonal to lines 106. When a selected intersection between an input-term line 106 and an AND line 108 is programmed, then xe2x80x9cAND termsxe2x80x9d or xe2x80x9cproduct termsxe2x80x9d 110 are formed. The product terms 110 are then fed into OR gates 112 forming xe2x80x9csum termsxe2x80x9d 114.
As is understood in the art, product-terms are often implemented with a wired-OR mechanism, where at each intersection of lines 106 and 108 programmable transistors 115 are used. A pull-up 116 is also used, as shown in the generalized circuit diagram of FIG. 2. Although the pull-up 116 is shown as a resistor in FIG. 2, frequently a passive pull-up is implemented with a biased P-channel transistor instead. It will be noted that when using the structure of FIG. 2, the AND gates 109 shown in FIG. 1 are not actually physically present, but instead in FIG. 1 AND gates 109 represent logically the function being performed.
A second type of PLA structure (sometimes referred to as a xe2x80x9cFull PLAxe2x80x9d) is shown in FIG. 3, having both a programmable AND array 104 and a programmable OR array 117. In other words, both product terms and sum terms can be programmed. Thus, the device of FIG. 3 can implement any set of combinational logic limited only by the number of inputs, outputs, and product terms.
Relative to the device of FIG. 1, the device of FIG. 3 sacrifices some speed, but has greater programming flexibility and is better for implementing state machines. As well, unlike the FIG. 1 device, in the FIG. 3 device, each product term can be used by, or shared among, all sum terms. Still, as shown in FIG. 4, some PLA devices create OR arrays where selected groups of the product terms are shared among selected groups of the sum terms.
Flexibility of PLA structures, including those of FIGS. 1 and 3, can be further enhanced by adding flip-flops 118 (shown in FIG. 3) to one or more of the outputs to create general-purpose sequential circuits. As shown in FIG. 5, inverted product terms such as !PT can also be fed back directly into the AND array. As used herein, complemented terms will be indicated with either a xe2x80x9c!xe2x80x9d or with an overbar, as is the practice in the art. As shown in FIG. 5a, when many product terms are inverted and fed back, it forms what is known as a NAND-NAND (or NOR-NOR) array.
Many PLA devices also include post-array logic structures as shown in FIG. 6. The most frequent need for such structures is to complement a logic functionxe2x80x94otherwise, to complement the function, one would have to resort to DeMorgan""s Law (!(AB)=(!A+!B)), typically resulting in a large number of product terms that would need to be programmed. XOR gates 120 are commonly used as such post-array structures. Inversion can be controlled by (1) a sum term representing a complex function (as for XOR gate 1201), (2) a single product term (as for XOR gate 1202), or (3) by a single logic value that can be programmed to a logical xe2x80x9c1xe2x80x9d (Vdd) or xe2x80x9c0xe2x80x9d (Vss) (as for XOR gate 1203).
Similarly, pre-array logic structures 122 are also often used as shown in FIG. 7. Such pre-array logic structures are often useful in performing arithmetic functions such as accumulators. Both post-array and pre-array logic structures are used to reduce the number of product terms that would otherwise be required, and hence allow the use of smaller and faster PLA devices.
Each of the conventional PLA structures described in FIGS. 1-7 is usually a discrete device and is programmable and reprogrammable by the user either using a specialized programming device or in-system as is understood in the art. As should be understood in the art from FIGS. 1-7, there are numerous types of PLAs available and those described are exemplary only.
As alluded to above with the discussion of pre- and post-array structures, it is generally desirable to use the smallest PLA device available, for real-estate reasons as well as speed. To that end, xe2x80x9cPLA foldingxe2x80x9d has been studied and is described in Ferreira and Song, xe2x80x9cAchieving Optimality for Gate Matrix Layout and PLA Folding: a Graph Theoretic Approachxe2x80x9d, 1992. In general, PLA folding is a technique that, given a PLA, attempts to produce an equivalent PLA that occupies less space. For example, consider the following logic functions to be implemented by a PLA:
f6={overscore (v)}1v5+{overscore (v)}2{overscore (v)}3+v1v3+{overscore (v)}5
f7=v2v4+{overscore (v)}2{overscore (v)}4
These functions are shown implemented in a traditional PLA in FIG. 8, where the xe2x80x9cdotsxe2x80x9d represent a programmed connection. Through a series of matrix manipulation and rearranging of rows, the result of the folding is shown in FIG. 9. More details of this example can be found in Ferreira and Song (cited above). As shown in FIG. 9, the folded PLA is much more compact, retaining as much physical regularity as possible by causing the tiling of product term groupings.
Still, this PLA folding technique has gained little practical application. To effectively use folding, an engineer must know with relative certainty the functions to be programmed. And the freedom to make changes to the functionality is severely limited by the xe2x80x9cfolds.xe2x80x9d Moreover, PLAs are typically only available as discrete devices (e.g., PLDs) in fixed sizes with fixed characteristics. So while folding techniques might be useful in theory, there are essentially no devices using them.
A PLA in accordance with an embodiment of the invention is designed after knowing the initial logic to be implemented by the PLA. Once such logic is known, a PLA sized specifically to that logic is modelled. Then unnecessary programmable connections are removed creating a relatively small, but fast PLA to implement the given function. Additional programmable connections are then re-added to the model to allow for future reprogramming. Finally, the modelled PLA is constructed.
The result is a PLA that achieves a maximum amount of depopulation while still implementing a logic function and maintaining flexibility for future reprogramming. In addition a PLA in accordance with an embodiment of the invention can be built so that no matter what functionality is programmed, the performance characteristics for the device remain the same.
A PLA in accordance with an embodiment of the invention does not require a regular array structure. Therefore, such a PLA is flexible for place and route considerations, particularly when integrated with other logic in larger circuits.